package 每日一题;

import com.alibaba.fastjson.JSON;

import java.util.*;

public class No224基本计算器 {

    /**
     * 实现一个基本的计算器来计算一个简单的字符串表达式 s 的值。
     *
     * 示例 1：
     * 输入：s = "1 + 1"
     * 输出：2
     * 示例 2：
     * 输入：s = " 2-1 + 2 "
     * 输出：3
     * 示例 3：
     * 输入：s = "(1+(4+5+2)-3)+(6+8)"
     * 输出：23
     *  
     * 提示：
     * 1 <= s.length <= 3 * 105
     * s 由数字、'+'、'-'、'('、')'、和 ' ' 组成
     * s 表示一个有效的表达式
     */

    //通用解法,转为逆波兰式子,按个求解;  后方有参考Good解法
    public int calculate(String s) {

        List<String> arr=this.StringConvertList(s);

        Deque<String> stack=new ArrayDeque<>();

        int index=0;

        while (index< arr.size()){

            switch (arr.get(index)){
                case " ": continue;
                case "+":{
                    stack.addLast(arr.get(index));
                    break;
                }
                case "-":{
                    stack.addLast(arr.get(index));
                    break;
                }
                case "(":{
                    stack.addLast(arr.get(index));
                    break;
                }
                case ")":{

                    List<String> list=new ArrayList<>();
                    while (!stack.peekLast().equals("(")){
                        list.add(stack.pollLast());
                    }
                    //栈顶就是开括号
                    stack.pollLast();//吐出

                    Collections.reverse(list);//倒转后为正序

                    int sum=0;
                    boolean isAdd=true;
                    for (int i = 0; i < list.size(); i++) {
                        if(list.get(i).equals("+")){
                            isAdd=true;
                        }else if (list.get(i).equals("-")){
                            isAdd=false;
                        }else{
                            //数字
                            if(isAdd){
                                sum+=Integer.parseInt(list.get(i));
                            }else{
                                sum-=Integer.parseInt(list.get(i));
                            }
                        }
                    }
                    stack.addLast(String.valueOf(sum));
                    break;
                }
                default:{
                    //数字
                    stack.addLast(arr.get(index));
                }
            }
            index++;
        }

        //栈中就是完全的数字
        List<String> list=new ArrayList<>();
        while (!stack.isEmpty()){
            list.add(stack.pollLast());
        }
        //栈顶就是开括号
        stack.pollLast();//吐出

        Collections.reverse(list);//倒转后为正序

        int sum=0;
        boolean isAdd=true;
        for (int i = 0; i < list.size(); i++) {
            if(list.get(i).equals("+")){
                isAdd=true;
            }else if (list.get(i).equals("-")){
                isAdd=false;
            }else{
                //数字
                if(isAdd){
                    sum+=Integer.parseInt(list.get(i));
                }else{
                    sum-=Integer.parseInt(list.get(i));
                }
            }
        }

        return sum;
    }

    private List<String> StringConvertList(String str){
        List<String> list=new ArrayList<>();
        StringBuilder sb= new StringBuilder();
        for (int i = 0; i < str.length(); i++) {
            if(str.charAt(i)==' '){
                continue;
            }else if(str.charAt(i)=='('||str.charAt(i)==')'||str.charAt(i)=='-'||str.charAt(i)=='+'){
                if(sb.length()!=0){
                    list.add(sb.toString());
                    sb.delete(0,sb.length());//清空
                }
                list.add(String.valueOf(str.charAt(i)));
            }else{
                sb.append(str.charAt(i));
            }
        }
        if(sb.length()!=0) {
            list.add(sb.toString());
        }
        return list;
    }

    //参考解法  有点不通用,还是用为我的通用逆波兰式吧。
    public int calculateGood(String s) {
        Deque<Integer> ops = new LinkedList<>();
        ops.push(1);
        int sign = 1;

        int ret = 0;
        int i = 0;
        while (i < s.length()) {
            if (s.charAt(i) == ' ') {
                i++;
            } else if (s.charAt(i) == '+') {
                sign = ops.peek();
                i++;
            } else if (s.charAt(i) == '-') {
                sign = -ops.peek();
                i++;
            } else if (s.charAt(i) == '(') {
                ops.push(sign);
                i++;
            } else if (s.charAt(i) == ')') {
                ops.pop();
                i++;
            } else {
                long num = 0;
                while (i < s.length() && Character.isDigit(s.charAt(i))) {//isDigit 字符是否为数字
                    //数字连续,不怕,有*10
                    num = num * 10 + s.charAt(i) - '0';
                    i++;
                }
                ret += sign * num;
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        No224基本计算器 n=new No224基本计算器();
        int result = n.calculate("");
        System.out.println(result);
    }

}
